package main

import "fmt"

/*
两两交换链表中的结点
 */
type ListNode struct {
	Val int
	Next *ListNode
}

func Swap(head *ListNode) *ListNode {
	// 虚拟节点
	dump := &ListNode{}
	dump.Next = head
	pre := dump
	for head != nil && head.Next != nil {   // 至少有两个结点才交换
		next := head.Next
		head.Next = next.Next
		next.Next = head
		pre.Next = next

		pre = head
		head = head.Next
	}
	return dump.Next
}

func main() {
	head := &ListNode{Val:1}
	head.Next = &ListNode{Val:2}
	head.Next.Next = &ListNode{Val:3}
	head.Next.Next.Next = &ListNode{Val:4}

	res := Swap(head)
	for res != nil {
		fmt.Printf("%5d", res.Val)
		res = res.Next
	}

}
